package done.easy_601_700;

import com.study.common.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 687. Longest Univalue Path 最长同值路径
 * <p>
 * 给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
 * 注意：两个节点之间的路径长度由它们之间的边数表示。
 * <p>
 * 示例 1:
 * 输入:
 * 5
 * / \
 * 4   5
 * / \   \
 * 1   1   5
 * <p>
 * 输出: 2
 * <p>
 * 任何一个节点如果在最长路径中，只能是下面两个情况
 * <p>
 * 【5】                 【5】
 * /  \                 /   \
 * 5    5      或       5    null
 * /     \              /
 * 5       5            5
 * left + right       max(left, right)
 * 【1 平躺】             【2 纵贯】
 *
 * @author wangxiaozhe
 */
@Slf4j
@SuppressWarnings("all")
public class LongestUnivaluePath {

    @SuppressWarnings("all")
    public int longestUnivaluePath(TreeNode root) {
        // 190325 first
        // 190329 second 看答案做了3次
        // 190402 third 没有真正理解 看答案做了两次
        // 190510 fouth 直接看没思路了，看了一遍答案之后做出来的
        // 190515 fifth 思路都对，算法几乎写出来了。边界值没做好判断
        return -1;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(5,
                new TreeNode(4,
                        1, 1), new TreeNode(5,
                null, new TreeNode(5,
                5, 6)));
        info(longestUnivaluePath(root));
    }
}







































/*
private int maxL = 0;

public int longestUnivaluePath(TreeNode root) {
    / **
     解题思路类似于124题, 对于任意一个节点, 如果最长同值路径包含该节点, 那么只可能是两种情况:
     1. 其左右子树中加上该节点后所构成的同值路径中较长的那个继续向父节点回溯构成最长同值路径
     2. 左右子树加上该节点都在最长同值路径中, 构成了最终的最长同值路径
     需要注意因为要求同值, 所以在判断左右子树能构成的同值路径时要加入当前节点的值作为判断依据
     ** /
    if(root == null) return 0;
    getMaxL(root, root.val);
    return maxL;
}

private int getMaxL(TreeNode r, int val) {
    if(r == null) return 0;

    // 判断1：左侧最长同值节点
    int left = getMaxL(r.left, r.val);

    // 判断2：右侧最长同值节点
    int right = getMaxL(r.right, r.val);

    // 缓存3：（左、右节点的和）与（存储的最大值）比较，取最大
    maxL = Math.max(maxL, left + right); // 路径长度为节点数减1所以此处不加1

    // 返回4：左、右两侧最大的节点 + 1
    if(r.val == val) // 和父节点值相同才返回以当前节点所能构成的最长通知路径长度, 否则返回0
        return Math.max(left, right) + 1;

    return 0;
}
*/
